Người Sa Đà có nguồn gốc từ người Xử Nguyệt.[2] Năm Trinh Quán thứ 7 (633) thời Đường Thái Tông, thủ lĩnh bộ lạc Xử Nguyệt từng theo quý tộc Tây Đột Quyết A Sử Na Di Xạ đến Trường An. Sau đó, Xử Nguyệt bộ lệ thuộc Ất Bì Đốt Lục khả hãn. Năm 642, Ất Bì Đốt Lục khả hãn tiến công Y châu (伊州, nay là Cáp Mật, Tân Cương), cũng phái Xử Nguyệt bộ và Xử Mật bộ bao vây Thiên Sơn quân (trị sở ở tây bắc Thác Khắc Tốn, Tân Cương), song đều bị quân Đường đánh bại.[3]

Những năm Vĩnh Huy (653 hoặc 654) thời Đường Cao Tông, quân Đường tiêu diệt quân Tây Đột Quyết của A Sử Na Hạ Lỗ, Xử Nguyệt bộ cũng bị đánh bại. Năm 702, tại Đình châu (庭州, nay thuộc Cát Mộc Tát Nhĩ, Tân Cương), triều Đường thiết lập Bắc Đình đô hộ phủ, thủ lĩnh Sa Đà bộ Chu Da Kim Sơn do có công cùng quân Đường đánh bại người Thiết Lặc, được phong là "Kim Mãn châu đô đốc", thuộc quyền quản hạt của Bắc Đình đô hộ. Sau đó, con của Chu Da Kim Sơn là Chu Da Phụ Quốc do chịu áp lực từ Thổ Phồn nên đã đưa bộ lạc di cư về phía bắc đến Đình châu.

Sau loạn An Sử, Hồi Hột chiếm giữ khu vực Tân Cương ngày nay, Thổ Phồn cũng tận dụng thời cơ chiếm cứ Hà Tây, Lũng Hữu (nay thuộc Cam Túc). Người Sa Đà bị Hồi Hột áp bức nên chuyển sang nương tựa vào Thổ Phồn, đến năm 789 thì liên quân công chiếm Đình châu. Để ngăn ngừa Sa Đà và Hồi Hột câu kết, Thổ Phồn đã buộc người Sa Đà di cư đến Cam châu (甘州, nay thuộc Trương Dịch, Cam Túc), phong con của Chu Da Phụ Quốc là Chu Da Tận Trung (cụ của Lý Khắc Dụng) là "thống quân đại luận", thường dẫn quân Thổ Phồn tiên phong.